// easy

// 给定一个长度为n的数组nums，nums包含[0, n]中的n个数，要求找出[0, n]范围内没有出现在数组中的那个数

// nums中的数字是唯一的

// 思路1：  哈希表
// 将nums中所有元素插入到哈希表中，然后遍历[0, n]，找到缺失的数字，这里的哈希表也可以用长度为n+1的数组代替

function missingNumber(nums) {
    let numSet = new Set(nums)

    for (let i = 0; i < nums.length + 1; i++) {
        if (!numSet.has(i)) {
            return i
        }
    }
}

// 思路2：数学计算
// 已知[0, n]的求和结果为 n * (n+1)/2

var missingNumber2 = function(nums) {
    const n = nums.length;
    let total = Math.floor(n * (n + 1) / 2);
    let arrSum = 0;
    for (let i = 0; i < n; i++) {
        arrSum += nums[i];
    }
    return total - arrSum;
};

// 思路3： 排序

var missingNumber3 = function (nums) {
    nums.sort((a, b) => a - b)
    const n = nums.length
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i) {
            return i
        }
    }
    return n
}
